import UIKit
/*
21-合并两个有序链表
 中文：https://leetcode-cn.com/problems/merge-two-sorted-lists/submissions/
 英文：https://leetcode.com/problems/merge-two-sorted-lists/
 时间复杂度：O(n + m)O(n+m) 。
 空间复杂度：O(1)O(1)
*/
public class ListNode {
    public var val: Int
    public var next: ListNode?
    public init(_ val: Int) {
        self.val = val
        self.next = nil
    }
}
 
class Solution {
    func mergeTwoLists(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
        var l1 = l1
        var l2 = l2
        let dummyHead = ListNode(Int.min)
        var current: ListNode? = dummyHead
        while let node1 = l1, let node2 = l2 {
            if node1.val < node2.val {
                current?.next = node1
                l1 = node1.next
            } else {
                current?.next = node2
                l2 = node2.next
            }
            current = current?.next
        }
        if l1 != nil {
            current?.next = l1
        } else if l2 != nil {
            current?.next = l2
        }
        return dummyHead.next
    }
}
